1. Field of the Invention
The present invention relates to synchronizing routing information among multiple intermediate network nodes; and in particular to avoiding two-way synchronization in certain cases.
2. Description of the Related Art
Networks of general purpose computer systems and specialized devices connected by external communication links are well known and widely used in commerce. The networks often include one or more network devices that facilitate the passage of information between the computer systems and devices. A network node is a network device or computer or specialized device connected by the communication links. An end node is a network node that is configured to originate or terminate communications over the network. An intermediate network node facilitates the passage of data between end nodes.
Communications between nodes are typically effected by exchanging discrete packets of data. Information is exchanged within data packets (also called messages herein) according to one or more of many well known, new or still developing protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other based on information sent over the communication links. Each packet typically comprises 1] header information associated with a particular protocol, and 2] payload information that follows the header information and contains information that may be processed independently of that particular protocol. The header includes information such as the source of the packet, its destination, the length of the payload, and other properties used by the protocol. Often, the data in the payload for the particular protocol includes a header and payload for a different protocol associated with a different layer of detail for information exchange.
The headers included in a packet traversing multiple heterogeneous networks, such as the Internet, typically include a physical (layer 1) header, a data-link (layer 2) header, an internetwork (layer 3) header and a transport (layer 4) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
The internetwork header provides information defining the source and destination address within the network. Notably, the path may span multiple physical links. The internetwork header may be formatted according to the Internet Protocol (IP), which specifies IP addresses of both a source and destination node at the end points of the logical path. Thus, the packet may “hop” from node to node along its logical path until it reaches the end node assigned to the destination IP address stored in the packet's internetwork header.
Routers and switches are intermediate network nodes that determine which communication link or links to employ to support the progress of data packets through the network. A network node that determines which links to employ based on information in the internetwork header (layer 3) is called a router.
Some protocols pass protocol-related information among two or more network nodes in special control packets that are communicated separately and which include a payload of information used by the protocol itself rather than a payload of data to be communicated for another application. These control packets and the processes at network nodes that utilize the control packets are said to be in another dimension, a “control plane,” distinct from the “data plane” dimension that includes the data packets with payloads for other applications at the end nodes.
A routing protocol only exchanges control plane messages used for routing data packets sent in a different routed protocol (e.g., IP). A portion of a network under the network administration of a single authority, such as an enterprise or Internet service provider (ISP) is called a domain or an autonomous system (AS). To reduce the consumption of network resources and improve scalability, some routing protocols send only summarized routing information. Routing information for an AS is summarized at its boundaries with one or more other ASs at intermediate network nodes called border gateway nodes or border gateway (BG) routers. Routing information shared within the borders of one AS is exchanged using an interior gateway protocol (IGP). Example IGPs include the link state protocols such as the intermediate system to intermediate system (IS-IS) protocol and the open shortest path first (OSPF) protocol. Another IGP, developed by Cisco Systems of San Jose, Calif. for use in its routers, is the Enhanced Interior Gateway Routing Protocol (EIGRP). Some of the link-state protocols divide an autonomous system into multiple areas, flood all data for a unified routing database within an area, but send only summarized information between areas. Some IGPs, like EIGRP, send only summary information from each intermediate network node in the autonomous system.
After a topology or configuration change, for example, when a central processing unit (CPU) in a router fails and is replaced by a standby CPU, an EIGRP router resynchronizes its information about network topology using a graceful restart (GRS) procedure. The network topology information indicates what destination nodes can be reached through which routers in the network. The EIGRP use a vector metric to determine the cost of reaching any destination from any router, and that cost is included with the topology information in routing tables, a portion of which reside at each router. With the GRS procedure, the routers in the network can continue to forward messages for several seconds while the changed router updates its information about network topology and passes that information to affected routers. The procedure provides a feature called non-stop forwarding (NSF).
According to the GRS, a router that has detected a configuration or topology change initializes the GRS by sending an UPDATE message for the protocol (e.g., an EIGRP UPDATE message) with a restart synchronization (RS) bit ON and an initiating (INIT) bit ON to indicate a graceful restart is being started by that router (the initiating router). Neighboring routers (also called “peers') that receive this UPDATE message acknowledge the graceful restart with an UPDATE message in which the RS bit is ON but not the INIT bit. After the exchange of these two UPDATE messages, both the initiating router and the neighboring routers send the full topology table with vector metrics that each has stored locally. The topology table with vector metrics, called herein the routing table data, is exchanged using two-way (bi-directional) transfer of each node's entire routing table data during the synchronization (also called a “refresh”, a “restart synchronization” and a “re-synchronization” herein).
While suitable for GRS and NSF, there are some disadvantages of this approach. There are circumstances in which it is not necessary to send routing table data in both directions. Currently, EIGRP uses GRS with full, two-way transfer of routing tables even in these circumstances.
For example, when filters change at one router, only routing table data from one or more routers need to be exchanged, not all routing table data from all neighbors. A filter is a configured process at a router by which details of several routes are summarized (“aggregated”) to a particular degree before being advertised to other routers. A router can have an inbound filter, which is used to ignore advertisements for certain destinations from certain neighbors. A router can also have an outbound filter, which is used to prevent the advertisement of certain destinations to certain neighbors.
In addition, a router might be configured for aggregation by which a single routing advertisement is substituted for multiple other routing advertisements. This is similar to an outbound filter in being different for inbound and outbound advertisements, but differs from filtering in that rather than preventing a route from being advertised, a different route is advertised in place of a set of routes.
When inbound route filters change, there is no reason for a router to send again its routing table to its neighbors, because the outbound routes have not changed. Similarly, when an outbound filter or aggregation changes, it is desirable for the reconfigured router to send the entire new routing table to the one or two neighbors affected by the aggregation. However, those neighbors' routing tables have not changed, and there is no reason for a router to receive each neighbor's routing table. It is burdensome for the routers individually, and the network as a whole, to expend processing and communication bandwidth so that one or more neighbors respond to the update by sending all their routing table data. Network performance is noticeably affected by such unnecessary transfers.
Similarly, when an inbound filter changes, it is desirable for the reconfigured router to receive the entire routing tables from the one or two neighbors affected by the filter change. However, the router's own routing table has not changed, and it is burdensome for the routers individually, and the network as a whole, to expend processing and communication bandwidth so that the router with the changed filter participates in the update by sending its routing table data to all its neighbors. Network performance is noticeably affected by such unnecessary transfers.
Based on the foregoing, there is a clear need for techniques for synchronizing routing information between neighboring routers that do not involve two-way transfers with all neighbors.